package com.company.Algorihm;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}21:22
 */
public class ZoreOneBag {
    public static void main(String[] args) {
        int[] w = {1, 4, 3};
        int[] val = {1500, 3000, 2000};
        int[][] v = new int[w.length + 1][val.length + 1];//动态规划表
        int large = 4;//包的容量上限

        int path[][] = new int[val.length+1][large+1];
        //初始化动态规划表
        for (int i = 0; i < v.length; i++) {
            v[i][0] = 0;
        }
        for (int i = 0; i < v[0].length; i++) {
            v[0][i] = 0;
        }

        //进入动态规划表
        for (int i = 1; i < v.length; i++) {
            for (int j = 1; j < v[0].length; j++) {//表的横轴、可放入容量依次递增
                if (w[i - 1] > j) {
                    v[i][j] = v[i - 1][j];//如果要放入的货物重量大于表中内容就将上一行的值
                } else {
                    if (val[i - 1] + v[i - 1][j - w[i - 1]] > v[i-1][j]){
                        v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
                        path[i][j] = 1;
                    }else {
                        v[i][j] = v[i-1][j];
                    }
//                    v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);//动态规划公式
                }
            }
        }

        for(int i =0; i < v.length;i++) {
            for(int j = 0; j < v[i].length;j++) {
                System.out.print(v[i][j] + " ");
            }
            System.out.println();
        }


        int i = path.length - 1; //�е�����±�
        int j = path[0].length - 1;  //�е�����±�
        while(i > 0 && j > 0 ) { //��path�����ʼ��
            if(path[i][j] == 1) {
                System.out.printf("第%d个放入\n", i);
                j -= w[i-1]; //w[i-1]
            }
            i--;
        }
    }
}